The present invention relates generally to error correction decoders, and more particularly, to a modular Galois-field subfield-power integrated inverter-multiplier circuit that may be used to implement Galois-field division over GF(245).
The closest previously known solutions to the problem addressed by the present invention are disclosed in U.S. Pat. No. 4,975,867 entitled “Apparatus for dividing elements of a Galois Field GF(2QM)” issued to Weng, U.S. Pat. No. 5,612,910 entitled “Circuit for inverting elements of a finite field” issued to Meyer, U.S. Pat. No. 5,467,297 entitled “Finite field inversion” issued to Zook, and U.S. Pat. No. 5,379,243 entitled “Method and apparatus for performing finite field division” issued to Greenberger et al.
U.S. Pat. No. 4,975,867 discloses an apparatus and/or method which enables one to divide two elements, A and B, of GF(22M), that is, perform the operation B/A, by finding the multiplicative inverse of the divisor A, and then multiplying the inverse by the numerator, B. The multiplicative inverse, A−1, of A is found by computing a conversion factor, D, and then multiplying A by D to convert it to an element C, where C is also an element of a smaller Galois Field, GF(2M), which is a subfield of GF(22M). Specifically, C is equal to A2M+1), or A2M*A, in the field GF(22M). Next, the multiplicative inverse, C−1, of C in GF(2M) is found by appropriately entering a stored look-up table containing the 2M elements of GF(2M). The multiplicative inverse, C−1, of C is thereafter converted, by multiplying it by the conversion factor D calculated above, to the element of GF(22M) which is the multiplicative inverse, A−1, of the original divisor, A. The multiplicative inverse, A−1, of A is then multiplied by B to calculate the quotient, B/A.
U.S. Pat. No. 5,612,910 discloses a circuit for inverting a number of n bits of a finite field of 2n=N+1 elements comprises a first circuit for raising to the power t=2n/2 receiving the number to invert. A first complete multiplier receives the number to invert and the output of the circuit for raising to the power t. A second circuit provides the product of the output of the circuit for raising to the power t and the inverse of the output of the first complete multiplier.
U.S. Pat. No. 5,467,297 discloses an inversion circuit (212) determines an inverse B−1 of an m-bit symbol B, the symbol B being expressed in a dual basis representation. Inversion circuit (212) includes an iterative convolution circuit (124A, 124B, 124C) to which the symbol B is applied and which generates and stores electrical signals corresponding to an m-bit value A. The value A is in a first basis representation and is generated by the convolution circuit such that an inner product of A and αkB is equal to 0 for k<m−1. A feedback circuit (128) is provided for enabling the convolution circuit to perform a convolution with an α multiple of B. A multiplier circuit (102) is connected to the convolution circuit and generates electrical output signals corresponding to the product of the value A and α−t. The electrical output signals from the multiplier represent Aα−t=B−1 (i.e., the inverse of the m-bit symbol B in the first basis representation). When necessary, the m-bit value A is bit-positionally justified, either by operating the convolution circuit as a shift register or by loading the value A into a shift register (132).
U.S. Pat. No. 5,379,243 discloses an apparatus and method are provided for simplifying a finite field division, including inputs for the initial condition signals a(x), b(x), and p(x), and providing at an output node the signal c(x), where c(x)=a(x)/b(x) without intermediate inverter circuitry for finding 1/b(x). A reference register initialized to b(x), and a divider register initialized to a(x). Both registers are manipulated in parallel by a logic circuit which responds to the contents of the reference register, converting its contents to 1. By applying the same manipulations to the divider register, its contents are converted from a(x) to a(x)/b(x). One embodiment of a finite field divider according to the present invention is used to provide a single finite field division of a single set of values a(x), b(x) and p(x). Another embodiment processes continuous streams of a(x), b(x) and p(x) values, to provide a continuous stream of c(x) values delayed by a calculation time. In another embodiment, p(x) is not a stream of values, but a constant either applied to the p(x) input of the finite field divider circuit or a constant defined by fixed circuit elements within the divider circuit.
However, known prior art approaches do not combine power inversion and subfield techniques are not combined to carry out the multiplicative inverse computation. Also, known prior art approaches do not simultaneously carry out multiplicative inversion and multiplication operations in parallel using a modular structure to increase the speed with which a full division operation can be carried out. Prior art approaches do not have a modular structure that allows natural pipelining of data and provide for increased clock speed. Furthermore, prior art approaches do not have a modular structure that eases circuit design, testing and implementation. Also, prior art approaches do not provide for a circuit that is completely asynchronous.
Accordingly, it is an objective of the present invention to provide for a modular Galois-field subfield integrated inverter-multiplier circuit for use in performing Galois-field division. It is also an objective of the present invention to provide for a modular Galois-field subfield integrated inverter-multiplier circuit that may be specifically used to perform Galois-field division over GF(245).